public class ReverseBetween {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode leftHead = head;
        ListNode leftTail = null;
        ListNode midHead = null;
        ListNode midTail = null;
        ListNode rightHead = null;
        ListNode cur = head;
        int index = 1;
        while (cur != null) {
            if (index == m - 1) {
                leftTail = cur;
            } else if (index == m) {
                if (index == n) {
                    return head;
                }
                midHead = cur;
            } else if (index == n) {
                midTail = cur;
            } else if (index == n + 1) {
                rightHead = cur;
                break;
            }
            cur = cur.next;
            index++;
        }
        midTail.next = null;
        ListNode newMidHead = reverseList(midHead);
        midHead.next = rightHead;
        if (leftTail != null) {
            leftTail.next = newMidHead;
            return leftHead;
        } else {
            return newMidHead;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

//    public static void main(String[] args) {
//        ListNode head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);
//        head.next.next.next.next = new ListNode(5);
//        ReverseBetween reverseBetween = new ReverseBetween();
//        ListNode newHead = reverseBetween.reverseBetween(head, 2, 4);
//    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(5);
        ReverseBetween reverseBetween = new ReverseBetween();
        ListNode newHead = reverseBetween.reverseBetween(head, 1, 1);
    }
}
